package week1;

import java.util.Stack;

public class UndiredGraph extends Graph {

	public UndiredGraph(int size) {
		super(size);
	}

	@Override
	public void addE(int u, int v) {
		matrix[u][v]++;
		matrix[v][u]++;
	}

	@Override
	public int deg(int u) {
		int s = 0;
		for (int i = 0; i < this.size(); i++) {
			s += matrix[u][i];
		}
		return s;
	}

	@Override
	public int numofDeg() {
		int s = 0;
		for (int j = 0; j < this.size(); j++) {
			s += deg(j);
		}
		return s / 2;
	}

	@Override
	public boolean lienThong(int u) {
		Stack<Integer> stack = new Stack<Integer>();
		boolean[] visit = new boolean[this.size()];
		boolean cont = true;
		int v = 0;
		while (cont) {
			visit[v] = true;
			
				for (int i = 0; i < matrix.length; i++) {
					if (matrix[v][i] != 0 && !visit[i]) {
						stack.push(v);
						stack.push(i);
						break;
					}
				}
				if (!stack.empty()) {
					v = stack.pop();
				}else{
					cont=false;
				}

			}
		
		
		return kiemTra(visit);

	}

	private boolean kiemTra(boolean[] visit) {
		for (int i = 0; i < visit.length; i++) {
			if (!visit[i])
				return false;
		}
		return true;
	}

}
